InfoMagic Standards 1994 January/InfoMagic Standards - January 1994.iso/misc/merit/noop/papers/citycode

Text File | 1992-03-05 | 16KB | 297 lines

                  City Codes: An Alternative Scheme for
                   OSI NSAP Allocation in the Internet


                             Stephen Deering
                     Xerox Palo Alto Research Center
                             January 7, 1992



         INCOMPLETE, WORKING DRAFT -- PLEASE DO NOT REDISTRIBUTE.

       [Author's notes to himself are enclosed in square brackets.]



1  Introduction

We propose a scheme for allocating OSI NSAP addresses (``NSAPs'', for
short) for use in the Internet, as an alternative to the scheme recommended
in RFC-1237 [Colella et al.].  The essence of our scheme is that the NSAPs
allocated to a particular ``leaf'' routing domain, such as a campus, a
corporate site, or a personal residence, have a prefix which identifies the
country and city in or near which the leaf domain attaches to a transit
routing domain, such as a regional or wide-area network.  Such NSAPs are
similar to plain old telephone numbers, which start with country and city
codes (or ``area codes'' in North America; we forgo the ``area''
terminology to avoid confusion with the previous use of that word in OSI
routing protocols).  Unlike the current practice in the telephone system,
however, we allow more than one ``carrier'' to offer transit delivery
service into, out of, and within the geographic scope of a single city
code.  NSAPs based on city codes identify where leaf domains obtain their
transit service; they do not identify the carriers providing the service.

The city code scheme achieves the same goal as RFC-1237: it eliminates the
need for wide-area routing domains, such as national and international
backbones, to maintain and distribute routing information about large
numbers of leaf domains.  Wide-area routing is based simply on country and
city codes.

The main advantage of the city code scheme over RFC-1237 is that a leaf
domain may be switched from one transit provider to another, or may be
attached to a transit provider for the first time, without changing its
NSAPs---provided that the new attachment point is within the geographic
scope of the same city code.  This is not true of the RFC-1237 scheme,
since it requires that most leaf domains acquire their NSAPs out of a block
belonging to currently-attached transit provider.  Thus, using city codes,
a leaf domain is not ``locked-in'' to its current transit provider; it can
be switched to whichever provider offers the most desirable service without
the burden of reconfiguring all internal hosts and routers (only part of
which might yield to automated procedures) and without a lengthy transition
period during which two providers may have to be paid.  City codes also
handle some ``multi-homed'' leaf domains, that is, leaf domains attached to
more than one public transit service, more gracefully than the RFC-1237
approach.


2  Proposed NSAP Structure

We propose that NSAPs for a leaf domain be structured as follows:

        <country-code> <city-code> <domain-id> <intra-domain-part>

where:

  <country-code> is a numeric code identifying the country in which the
leaf domain attaches to a transit service.  It is not strictly necessary
that country codes be one-to-one with countries.  A single code may
identify a contiguous set of countries (perhaps arising from the break-up
of a larger country, like the U.S.S.R. or Canada).  A single country may
also have more than one country code (perhaps arising from the merger of
several independent countries, like East and West Germany, or the wider
European Community).  And a country code may be assigned to a non-country,
like Antarctica or the Moon.

  <city-code> is a numeric code identifying the geographical region within
a country, typically centered on a major metropolitan area (unless it
happens to be Antarctica or the Moon!), in which the leaf domain attaches
to a transit service.  A country would not be expected to have more than a
couple hundred city codes.  Unlike telephone area codes, a single large
city would not be partitioned into multiple, non-overlapping city codes,
although it would be permissible for two city codes to overlap,
geographically.

  <domain-id> is a numeric code identifying the particular leaf domain
within the city of the attachment point.  Every leaf domain in a city has a
unique domain ID, independent of the transit provider.  Strategies for
allocating domain IDs are discussed below.

  <intra-domain-part> is the part of the NSAP upon which the leaf domain
performs its internal routing.  In the case of a leaf domain using DIS10589
(the IS-IS intra-domain routing protocol), the intra-domain part would
consist of the Area ID, System ID, and NSAP Selector subfields.

There are a variety of ways of encoding this structure within an NSAP. A
simple encoding scheme, similar to the ANSI proposal described in RFC-1237,
would be as follows:

    1 octet AFI = 39
    2 octet Country Code  (ISO DCC)
    1 octet DFI = 2       (to identify this particular format)
    1 octet Reserved      (for possible growth of the city code field)
    1 octet City Code     (allows up to 256 cities per country)
    2 octet Reserved      (for possible growth of the domain ID field)
    3 octet Domain ID     (allows up to 16 million leaf domains per city)
    2 octet Area ID
    6 octet System ID
    1 octet NSAP Selector
   --
   20 octets total

[I wonder if there any possibility of shoehorning a version of this scheme,
with more carefully-crafted subfields, into the IP Class A address space,
to extend the useful life of IP?]


3  Routing through Transit Domains

We first consider the case of ``public'' transit routing domains that offer
to deliver packets anywhere in the ``global internet''.  Such routing
domains do not themselves reach everywhere---they may span only a single
metropolitan area or multiple cities, in one country or in multiple
countries---but through bilateral and multilateral agreements with other
transit domains (such as national and international backbones and various
regional and metropolitan networks), they are able to offer universal
delivery service.  It is this set of interconnected, public transit domains
that may be said to define the ``global internet''.

Under the city code scheme, each router in such a transit domain must
maintain routing table entries to enable it to reach any city in the global
internet.  Those entries may consist of interior routes to cities or
countries directly reachable within the domain, obtained through the
operation of a conventional intra-domain routing protocol, and exterior
routes to specific cities, to specific countries (with the city
unspecified), and to ``default'' countries, injected at the domain's
boundary routers by static configuration or an inter-domain routing
protocol.

The number of such inter-city route entries in any one router is expected
to be manageably small.  For a single-city regional, it may be just a
single ``default'' entry, pointing to a wide-area backbone.  For a larger
regional, there will be entries for each of the cities served by that
regional, plus zero or more country routes, plus a default.  National
backbones will probably have routes to all cities within one country, and
international backbones will probably have routes to all countries.  If by
nothing else, the number of such entries is bounded by the total number of
cities in the world.  [I wonder how many there are?]

A packet is routed towards its destination city via the inter-city route
entries, using the conventional ``longest-match'' algorithm to choose a
city-specific route over a country-only route.  Once the packet reaches a
router in the destination city, further routing is done using the domain ID
field.    The router at which the packet arrives in the destination city
may or may not belong to a transit domain that is directly serving the
destination leaf domain.  If it does, it will have a internal route for the
given domain ID.  If it does not, the router must have some other
information that will allow it to forward the packet to a transit domain
that does directly serve the destination.

[Here's comes the interesting bit, at last.  Hope it makes sense.]

In order for a packet to get shuttled to the right transit domain in the
destination city, all of the domains serving a single city must be
connected to each other, either directly or indirectly (through some other
transit service), and they must exchange information about which transit
domains serve which leaf domains.  The simplest way to exchange that
information is simply to have each transit domain export all of its leaf
domain routes to all of the other transitdomains serving the same city;
that should suffice for cities with only a few hundred leaf domains.
However, we may expect the number of leaf domains in a city eventually to
grow into the millions (when, someday, every telephone is replaced by a
router).  For large numbers of leaf domains, more efficient information
exchange is possible: once a day, say, each transit domain could simply
send a list of all of the leaf domain IDs it serves to each of its
neighboring domains.  The routers would then concatenate the lists from all
of the domains, and use the resulting list as an indirection table for
routing packets within the city: the domain ID of a packet's destination
would first be looked up in the indirection table to find out who serves
that ID, and then the routing table would be consulted to determine how to
reach the serving domain.  If the memory cost of storing the indirection
table becomes prohibitive, it could reasonably be stored on disk, with only
the recently-referenced domain IDs being cached in memory.  (The once a day
exchange rate implies that it would take at most one day for a leaf domain
to start receiving service from a new transit domain.)

The storage required for the list of domain IDs could be further reduced by
imposing some sub-structure on domain IDs, assuming that most leaf domains
will not, in fact, ever switch from their initial transit domain to some
other transit domain.  If that should be the case, then it would be
reasonable to hand out blocks of domain IDs to each transit domain serving
a city, structured as follows:

                   <transit ID> <serial no>

where <transit id> identifies the transit domain within the city, and
<serial no> is simply incremented each time a new leaf domain ID is to be
assigned by that transit domain.  A leaf domain would obtain a domain ID of
that form from the first transit domain to which it connected.  If the leaf
domain later switched to another transit, it would still keep the same
domain ID, but it would report that ID to its new transit domain.  Then,
each transit domain would only have to inform its neighbors of these
``exceptions'' (i.e., leaf domains whose domain ID's <transit ID> field did
not match their current transit provider), rather than complete lists of
all served leaf domains.

For ``semi-private'' transit domains, such as wide-area networks
constrained to serving a limited clientele, routing could be performed on
full <country-code><city-code><domain-id> prefixes, treating them as a flat
field.  Alternatively, a semi-private domain could take advantage of the
city code structure to achieve the same scalability benefits as the public
transit domains.  The only difference would be that, in the semi-private
case, if a packet arrives in its destination city and the router there does
not have an interior route to the destination leaf domain, the router would
simply drop the packet, it being addressed to an unauthorized destination.


4  Routing in Leaf Domains

Within a leaf domain, routing is normally performed using the NSAP fields
that follow the domain ID.  If a leaf domain attaches to more than one
transit domain in the same city, it need not obtain multiple NSAP
allocations; packets with the same destination NSAP may arrive via any of
the attached transit domains.  (The leaf domain may control which transit
domain it uses for outgoing traffic, based on the source and destination
addresses of the traffic, quality-of-service fields, time-of-day, or any
other information at hand, similar to the way modern office PBX systems
select carriers for off-site calls.  The choice of transit domain for
incoming traffic, however, is under the control of the source leaf domain
and all of the intermediate transit domains.  [Should I mention the
possibility of explicitly allocating multiple NSAP blocks with different
domain IDs for a multi-home domain, in order to control incoming traffic
via the addresses that are handed out to communicants?]).

A leaf domain may itself span multiple cities, or multiple countries.  An
example is a large private corporate internet interconnecting many branch
offices.  If such a domain attached to the ``public'' internet in only one
place, the NSAPs for all of the company's systems (or at least all systems
with external access privileges) would contain the city code for the
attachment point, regardless of where the systems themselves were located.
If the corporate domain were attached to the public internet in more than
one place, it would be reasonable for the systems inside the corporation to
take their NSAPs from their nearest point of attachment, as discussed in
RFC-1237.  This would mean the use of multiple NSAP prefixes (country,
city, and domain IDs) within the single corporate domain.  The intra-domain
routing protocol could be configured to know about the specific prefixes
belonging to the company, in order to keep intra-company traffic inside the
corporate internet.  The country and city structure of those NSAPs could be
exploited for their scalability benefits by the corporate routers.
Alternatively, the company could use an entirely separate NSAP address
space for its systems, in addition to the NSAPs obtained from any public
attachment points, similar to the way telephones in some large corporations
may be ``addressed'' by both a normal, public phone number, and a number
belonging to the corporation's own private phone system.  One advantage of
assigning both interior and exterior addresses to the company's systems
might to allow the exterior addresses and public connectivity to be used
for intra-company communication if the corporate internet should partition.


5  When NSAPs Change

Under the city code scheme, there are still occasions when it is necessary
for a leaf domain to change some or all of its NSAPs.  For example, if a
small company moves to a new city and attaches its routing domain there,
that domain will have to use new NSAPs.  However, such moves also entail
changes of phone numbers, fax numbers, postal addresses, etc., so the
change of NSAPs would not be unexpected or unreasonable.

If a company with a wide-area private internet adds a new attachment point
to the public internet, it is necessary to assign new NSAPs to some of the
company's systems if it is desired that those systems receive packets via
the new attachment point.  However, the new addresses may be introduced
gradually, and use of the old addresses may be allowed to continue for an
indefinite transition period.

Finally, if the country or city code of an attachment point should happen
to change, say, by annexation of the city by a hostile neighboring country,
leaf domain NSAPs would have to change.  That would probably be the least
of the worries.


[Should add some discussion of ``800 numbers'', mobile hosts, and
multicast.  Nothing surprising.]


References

[Colella et al.]  Colella R., Gardner E., and Callon, R.
                  Guidelines for OSI NSAP Allocation in the Internet.
                  RFC-1237, Network Working Group, July 1991.


------- End of Forwarded Message